﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Sort
{
    static class QSort
    {
        static void Main()
        {
            int[] arr = {1, 2, 3, 5, 0, 9, 8, 7, 6, 4};
            Random rd = new Random();
            for (int j = 0; j < 1000; j++)
            {
                for (int i = 0; i < 10; i++)
                {
                    arr[i] = rd.Next(20);
                }
                Sort(arr, 0, 9);
                if (!Utils.CheckOrderArray(arr))
                {
                    Console.WriteLine("error.");
                }
                Utils.WriteArr(arr);
            }

        }

        //public static void Sort(int[] arr, int beg, int end)
        //{
        //    if (beg >= end)
        //    {
        //        return;
        //    }

        //    int midVal = arr[beg];
        //    int idx = beg;
        //    for (int i = beg+1; i <= end; i++)
        //    {
        //        int temp = arr[i];
        //        if (temp <= midVal)
        //        {
        //            idx++;
        //            Utils.Swap(arr, idx, i);
        //        }
        //    }
        //    if (beg != idx)
        //    {
        //        Utils.Swap(arr, beg, idx);
        //    }

        //    Sort(arr, beg, idx-1);
        //    Sort(arr, idx+1, end);
        //}

        static public void Sort(int[] arr, int beg, int end)
        {
            if (beg >= end)
                return;

            if (end == beg + 1)
            {
                if (arr[beg] > arr[end])
                    Utils.Swap(arr, beg, end);
                return;
            }

            int first = beg;
            int last = end;
            int key = arr[beg];

            while (last > first)
            {
                if (arr[last] > key)
                {
                    last--;
                    continue;
                }

                if (arr[first] <= key)
                {
                    first++;
                    continue;
                }
                Utils.Swap(arr, first, last);
            }
            Utils.Swap(arr, beg, first);

            Sort(arr, beg, first - 1);
            Sort(arr, first + 1, end);
        }

        //static int division(int[] list, int left, int right)
        //{
        //    // 以最左边的数(left)为基准
        //    int value = list[left];
        //    while (left < right) {
        //        // 从序列右端开始，向左遍历，直到找到小于base的数
        //        while (left < right && list[right] >= value)
        //            right--;

        //        // 找到了比base小的元素，将这个元素放到最左边的位置
        //        list[left] = list[right];
 
        //        // 从序列左端开始，向右遍历，直到找到大于base的数
        //        while (left < right && list[left] <= value)
        //            left++;
        //        // 找到了比base大的元素，将这个元素放到最右边的位置
        //        list[right] = list[left];
        //    }
 
        //    // 最后将base放到left位置。此时，left位置的左侧数值应该都比left小；
        //    // 而left位置的右侧数值应该都比left大。
        //    list[left] = value;
        //    return left;
        //}

        //public static void Sort(int[] list, int left, int right) {
 
        //    // 左下标一定小于右下标，否则就越界了
        //    if (left < right) {
        //        // 对数组进行分割，取出下次分割的基准标号
        //        int value = division(list, left, right);
 
        //        // 对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值完整的排序
        //        Sort(list, left, value - 1);
 
        //        // 对“基准标号“右侧的一组数值进行递归的切割，以至于将这些数值完整的排序
        //        Sort(list, value + 1, right);
        //    }
        //}
    }
}
